1. Field of the Invention
This invention relates generally to the configuration of a complex nodal-type network and, more particularly, to a methodology for heuristically selecting, subject to given constraints, links interconnecting network nodes to thereby configure the network.
2. Description of the Background Art
Conceptually, a Virtual Private Network (VPN) is characterized by a set of connections among N nodes. The connections may assume any topology such as full-mesh, partial-mesh, or stars. The connections may be uni-directional, bi-directional, point-to-point or point-to-multipoint, symmetric or asymmetric. VPN connections are usually associated with a set of performance requirements typically summarized in a service level agreement (SLA). Given a VPN request by a customer, specified by a SLA, the VPN service-planning task involves finding network resource necessary to fulfill the VPN-SLA requirement. In this context, network resource is defined to be a set of links chosen for the realization of the requested VPN connections.
In a practical network, such as an ATM network or an IP MPLS network, multiple links normally exist between two nodes of such networks. Algorithms exist for finding the most efficient links satisfying a set of SLA requirements. An example of such an algorithm can be found in an article entitled “Finding the K Shortest Loopless Paths in a Network”, by J. Y. Yen, Management Science, 11 (1971), pages 712–716.
However, the problem for planning VPN is more involved due to the simultaneous requirement of a set of connections among N points. Suppose a VPN has connections 1, 2, . . . C. Suppose the VPN planner (which can be a software) attempts to find the optimum path, that is, a set of links (dependent on certain global criteria to be discussed later) connecting a given one of the N points with another one of the N points sequentially for connections 1, 2, 3 . . . . It is assumed that the first connection path is found by using the method described in the reference cited above. Next, the planner proceeds to find an optimum path for connection 2. By selecting a path to realize connection 2, the planner inevitably changes the available network resource and therefore the network state. This change upsets the optimum conditions for the previously selected path 1 and renders such selection non-optimum. This simple illustration of the so-called “sequential approach” suggests that a global optimal solution cannot be obtained by a straightforward sequential application of the same algorithm that produces an optimal solution for a single connection. Of course, an exhaustive search of every possible combination of all the k paths for all the C connections will theoretically yield the optimum solution. Such approach, however, would be prohibitively time-consuming and computationally-consuming (non-polynomial time).
Thus, a need exists in the art for a systematic procedure to configure a complete VPN given a specified SLA. As part of this procedure, it is necessary to obtain a tractable, effective solution that gives “close-to-optimum” results with negligible computational effort. “Close-to-optimum” means that the search result determines a feasible global minimum.